package com.hw3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class ParseExpression {

	public static List<String> stringTokenizer(String input){
		int len=input.length();
		List<String> inp=new ArrayList<String>();
		for(int i=0,j=0;i<len;i++){
			if(i+1!=len && ((input.charAt(i)-'0'<10 && input.charAt(i)-'0'>=0) || input.charAt(i)=='.') &&
					((input.charAt(i+1)-'0'<10 && input.charAt(i+1)-'0'>=0) || input.charAt(i+1)=='.')){
				continue;
			}
			else{
				inp.add(input.substring(j,i+1));
				j=i+1;
			}
		}
		return inp;
	}

	public static void testStringTokenizer(){
		String s="1+(20.7*3)-7/(7-5)";
		List<String> inp=stringTokenizer(s);
		for (String string : inp) {
			System.out.print(string+" ");
		}
	}

	public static Map<String,Integer> precedenceOrder(){
		Map<String,Integer> pre=new HashMap<String,Integer>();
		String[] operator={"^","/","*","+","-"};
		for(int i=0;i<operator.length;i++){
			pre.put(operator[i], operator.length-i);
		}
		return pre;
	}

	public static boolean precedenceOrder(Map<String,Integer> pre,String s1,String s2){
		return pre.get(s1)>pre.get(s2);
	}
	private static Double getOperationValue(Double first, Double last,String operatr) {
		switch (operatr){
		case "+":return first+last;
		case "/":return first/last;
		case "*":return first*last;
		case "-":return first-last;
		case "^":return Math.pow(first, last);
		}
		return null;
	}


	public static void shuntingYardRPN(String input){
		List<String> inp=stringTokenizer(input);
		Stack<String> operand=new Stack<String>();
		List<String> rpn=new ArrayList<String>();
		Map<String,Integer> prec=precedenceOrder();
		for(String ch:inp){
			if("(".equals(ch))
				operand.add(ch);
			else if(")".equals(ch)){
				while(!"(".equals(operand.peek())){
					rpn.add(operand.pop());
				}
				operand.pop();
			}
			else if(!prec.containsKey(ch))
				rpn.add(ch);
			else if(prec.containsKey(ch)){
				while(!operand.empty() && prec.containsKey(operand.peek()) && precedenceOrder(prec, operand.peek(),ch)){
					rpn.add(operand.pop());
				}
				operand.push(ch);
			}

		}
		while(!operand.isEmpty())
			rpn.add(operand.pop());
		for(String ch:rpn){
			System.out.print(ch+",");
		}
		System.out.println();
		return;
	}

	public static void testshuntingYard(){
		String s="1+(20.7*3)-7/(7-5)";
		shuntingYardRPN(s);
	}

	/*
	 * get maximum or minimum value- recursion
	 */
	public static String getMaximumValue(String input){
		List<String> inp=stringTokenizer(input);
		Map<String,Integer> prec=precedenceOrder();
		assert(inp.size()%2==0);
		int i=0;
		for(String ch:inp){
			if(i%2==0){
				try{
					Double.parseDouble(ch);
				}
				catch(Exception e){
					e.printStackTrace();
					return "Malformed Expression";
				}
			}
			else
				assert(prec.containsKey(ch));
			i++;
		}

		return  getMaximumValue(inp,0,inp.size()-1).max;
	}

	private static Pair getMaxMinValues(Pair left, Pair right, String op){

		Double minn;
		Double maxx;
		if("/".equals(op) || "-".equals(op)){
			minn=getOperationValue(Double.parseDouble(left.min),Double.parseDouble(right.max),op);
			maxx=getOperationValue(Double.parseDouble(left.max),Double.parseDouble(right.min),op);
		}
		else{
			minn=getOperationValue(Double.parseDouble(left.min),Double.parseDouble(right.min),op);
			maxx=getOperationValue(Double.parseDouble(left.max),Double.parseDouble(right.max),op);
		}
		return new Pair(minn.toString(),maxx.toString());
	}
	private static Pair getMaximumValue(List<String> inp, int i, int j) {
		if(i==j)
			return new Pair(inp.get(i),inp.get(j));
		if(j-i==2){
			Double first=Double.parseDouble(inp.get(i));
			Double second=Double.parseDouble(inp.get(j));
			Double val=getOperationValue(first,second,inp.get(i+1));
			return new Pair(val.toString(),val.toString());
		}
		Double minval=Double.MAX_VALUE;
		Double maxval=Double.MIN_VALUE;
		for(int k=i;k<j;k=k+2){
			Pair left=getMaximumValue(inp,i,k);
			Pair right=getMaximumValue(inp,k+2,j);
			Pair cur=getMaxMinValues(left, right, inp.get(k+1));

			if(minval>Double.parseDouble(cur.min))
				minval=Double.parseDouble(cur.min);
			if(maxval<Double.parseDouble(cur.max))
				maxval=Double.parseDouble(cur.max);
		}
		return new Pair(minval.toString(),maxval.toString());
	}

	public static void testgetMaximumValue(){
		String inp="1+3*7-8/2";
		System.out.println(getMaximumValue(inp));
	}
	
	/*
	 * get maximum or minimum value- DP
	 */
	public static String getMaximumValueDP(String input){
		List<String> inp=stringTokenizer(input);
		Map<String,Integer> prec=precedenceOrder();
		int sizz=inp.size();
		assert(sizz%2==1);
		int i=0;
		for(String ch:inp){
			if(i%2==0){
				try{
					Double.parseDouble(ch);
				}
				catch(Exception e){
					e.printStackTrace();
					return "Malformed Expression";
				}
			}
			else
				assert(prec.containsKey(ch));
			i++;
		}

		//create array and populate
		int numNum=sizz/2+1;
		Pair[][] arr=new Pair[numNum][numNum];
		for(i=0;i<sizz;i=i+2){
			arr[i/2][i/2]=new Pair(inp.get(i),inp.get(i));
		}
		
		//iterative table filling
		int diff=0;
		for(int p=1;p<numNum;p++){
			diff=diff+2;
			for(i=0;i<sizz-diff;i=i+2){
				int j=i+diff;
				for(int k=i;k<j;k=k+2){
					int ii=i/2;
					int jj=j/2;
					arr[ii][jj]=new Pair();
					arr[ii][jj] = getMaxMinValues(arr[ii][jj-1],arr[ii+1][jj],inp.get(k+1));
				}
			}
		}
		return arr[0][numNum-1].max;
	}
	
	public static void testgetMaximumValueDP(){
		String inp="1+3*7-8/2";
		System.out.println(getMaximumValueDP(inp));
	}
	
	

}